Reverse a Linked List using Recusion Algorithm
The Reverse a Linked List using Recursion Algorithm is an efficient technique for reversing the elements of a singly linked list in place, without the need for any additional data structures or memory allocation. This algorithm makes use of recursion, which is a programming approach where a function calls itself as a subroutine to solve a smaller instance of the same problem, until it reaches the base case. The main idea behind this algorithm is to traverse the linked list from the head to the tail using a recursive function, and then reverse the pointers of each node while backtracking from the tail to the head.
The algorithm starts by checking if the head of the linked list is null or if there is only one element, in which case, the list is already reversed and no further action is needed. If there are more elements in the list, the algorithm calls the recursive function with the next node as the new head, effectively traversing the list until the tail node is reached. Once the tail node is reached, the base case is encountered and the recursion starts to unwind. During the unwinding process, the algorithm reverses the direction of the pointers of each node by setting the next node's next pointer to point to the current node, effectively reversing the linked list. This process continues until the original head node is reached, at which point the algorithm sets its next pointer to null, completing the reversal of the linked list.
#include <iostream>
using namespace std;
struct node
{
int val;
node *next;
};
node *start;
void insert(int x)
{
node *t = start;
if (start != NULL)
{
while (t->next != NULL)
{
t = t->next;
}
node *n = new node;
t->next = n;
n->val = x;
n->next = NULL;
}
else
{
node *n = new node;
n->val = x;
n->next = NULL;
start = n;
}
}
void reverse(node *p, node *q)
{
if (q->next == NULL)
{
q->next = p;
p->next = NULL;
start = q;
return;
}
else
{
reverse(q, q->next);
q->next = p;
p->next = NULL;
}
}
void show()
{
node *t = start;
while (t != NULL)
{
cout << t->val << "\t";
t = t->next;
}
}
int main()
{
insert(1);
insert(2);
insert(3);
insert(4);
insert(5);
insert(6);
reverse(start, start->next);
show();
return 0;
}
